/*
 *
 Minimum Size Subarray Sum:

 Given an array of n positive integers and a positive integer s, find the
 minimal length of a subarray of which the sum ≥ s. If there isn't one, 
 return 0 instead.

 For example, given the array [2,3,1,2,4,3] and s = 7,
 the subarray [4,3] has the minimal length under the problem constraint.
 *
 *
 *author : Howland Dong
 *date: 2015-10-6
 *note: not an efficient solution
 *
 *
 */


#include <sys/time.h>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int minSubArrayLen(int s, vector<int>& nums) {

  if (nums.size() <= 0 ) {
    return 0;
  }

  vector<int> sum(nums.size(), 0);
  int tmpLen = 1;

  for (tmpLen = 1; tmpLen <= nums.size(); ++tmpLen) {
    for (int i = 0; i <= nums.size() - tmpLen; ++i) {
      sum[i] = sum[i] + nums[tmpLen + i - 1];
      if (sum[i] >= s) {
        return tmpLen;
      }
    }
  }

  return 0;
}



int main(int argc, char *argv[]) {

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  vector<int> v1 = {2,3,1,2,4,3};
  vector<int> v2;
  int ret = minSubArrayLen(7, v1);
  cout << ret << endl;

  int time2 = gettimeofday(&tv2, &tz);
  cout << "time consuming(local machine/leetcode server):" << endl
    << "leetcode server time consuming should be less than 500ms" << endl
    << tv2.tv_usec - tv1.tv_usec << "us/"
    << 0.11*( tv2.tv_usec - tv1.tv_usec ) << "ms" << endl;



  return 0;
}





